home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / GRAPHICS / OTMSORT.ZIP / OTMSORT.TXT
Encoding:
Text File  |  1995-07-06  |  20.9 KB  |  457 lines

  1.  
  2.         OTMSORT.TXT - Sorting algorithms for 3d graphics
  3.  
  4.         released 2-20-95
  5.         by Voltaire/OTM [Zach Mortensen]
  6.  
  7.         email -
  8.         mortens1@nersc.gov
  9.  
  10.  
  11. INTRODUCTION
  12.  
  13.                 During the past month, I have received many inquiries
  14.         concerning sorting algorithms used in 3d engines, which are the
  15.         fastest, etc.  I figured I could save myself some IRC and email
  16.         writing time by compiling a text on the matter that would
  17.         explain everything in a concise manner.  In this text, I will
  18.         describe various sorting algorithms, and the pros and cons of
  19.         each.  This primarily covers variations of the radix sort,
  20.         which I have found to be the fastest algorithm.
  21.  
  22.                 A fast sort is critical to a fast 3d engine, perhaps
  23.         even more critical than a fast poly fill.  In the first version
  24.         of my 3d engine, I implemented a linear sort (quite a misnomer
  25.         actually).  When I began optimizing, I found that the sort was
  26.         a huge bottleneck.  After I switched to a z-buffered drawing
  27.         scheme which eliminated the sorting algorithm, my code ran
  28.         about 7 times faster than it had before.
  29.  
  30.                 I quickly discovered that z-buffering was not the
  31.         fastest method either.  It requires an enormous amount of
  32.         memory accesses per polygon, which can be very very slow on a
  33.         machine without a fast bus and writeback cache.  I needed to
  34.         find an algorithm that would allow me to sort my polygons with
  35.         the fewest number of memory accesses.
  36.  
  37.                 The radix sort was the answer I had been looking for.
  38.         The radix sort is adventageous over all other sorting
  39.         algorithms because its sorting time as a function of the number
  40.         of data to be sorted is linear.  The sorting time as a function
  41.         of number of data in most commonly used sorts is exponential,
  42.         which causes a tremendous slowdown when a large number of
  43.         polygons are being sorted.
  44.  
  45.  
  46. THE BUBBLE SORT
  47.  
  48.         Here is an example of a bubble sort
  49.  
  50.  
  51.                 for (count = 0; count < numData; count++)
  52.                     for (index = 0; index = numData; index++)
  53.                         if (data[count] > data[index])
  54.                             swap(data[count], data[index]);
  55.  
  56.  
  57.                 This is by far the simplest sorting algorithm known to
  58.         man.  It is also the most inefficient sorting algorithm that
  59.         could possibly be used, literally.  In the bubble sort, each
  60.         element of the set is compared with all other elements,
  61.         yeilding a total of numData * numData iterations through the
  62.         sorting loops.  As you can see, this is a quadratic function.
  63.         By doubling the number of data to be sorted with a bubble sort,
  64.         the sorting time increases FOUR TIMES.  The bubble sort is a
  65.         definite no no if you are remotely interested in speed.
  66.  
  67.  
  68. THE "LINEAR" SORT
  69.  
  70.                 The linear sort was taught to me in my High School
  71.         pascal class.  It was a much faster sort than the bubble sort
  72.         in our examples which required us to sort a set of not more
  73.         than 20 numbers, so it was the first sort I implemented in my
  74.         3d code.  However, a closer look shows that it is nothing more
  75.         than a slight variation of the bubble sort algorithm, with a
  76.         slight increase in the performance.
  77.  
  78.                 for (count = 0; count < numData; count++)
  79.                 {
  80.                     x = count;
  81.                     for (index = count + 1; index < numData; index++)
  82.                         if (data[index] > data[x])
  83.                             x = index;
  84.  
  85.                     if (x > count)
  86.                         swap(data[x], data[count]);
  87.                 }
  88.  
  89.  
  90.                 This algorithm yeilds numData iterations through the
  91.         outer loop, with an average of (numData / 2) iterations through
  92.         the inner loop per outer loop iteration.  Therefore, the total
  93.         number of iterations through the inner loop is (numData *
  94.         numData) / 2.  This total is half the total of the bubble sort,
  95.         but it is still a quadratic relationship.  By doubling the
  96.         number of data, the sort time is doubled.  This seems to be a
  97.         linear increase (hence the name linear sort), but it is not.
  98.         If the size of the data is increased by a factor of 4, the sort
  99.         time is increased by a factor of 8 (4 * 4 / 2).  An increase by
  100.         a factor of 8 in the size of the data will result in the sort
  101.         time increasing by a factor of 32 (8 * 8 / 2). So, this sort is
  102.         nearly as bad as the bubble sort when sorting VERY large data
  103.         sets.
  104.  
  105.  
  106. THE RADIX SORT
  107.  
  108.                 If you have never heard of the radix sort, you are not
  109.         alone.  If you learned about the radix sort in a programming
  110.         class and thought it was totally useless, you are like I was.
  111.         The way the radix sort is usually taught in classes is
  112.         efficeint for everything but computers.  This is because the
  113.         textbooks usually use base 10 (decimal), which is extremely
  114.         foreign and difficult to implement in a computer.  The idea
  115.         behind a radix sorting algorithm is to sort the data by each
  116.         radix, starting with the least significant and moving to the
  117.         most significant.  This is best illustrated by an example.
  118.  
  119.                 First off, it helps to define radix.  A radix is a
  120.         'place' in a number.  The base 10 radices have common names (1s
  121.         place, 10s place, 100s place, etc), but the concept can be
  122.         extended to numbers of any base.  Consider the base 10 number
  123.         32768.  The value of the first (least significant) radix is 8,
  124.         the second is 6, the third is 7, the fourth is 2, and the fifth
  125.         is 3.  Now consider the base 16 (hexadecimal) number 3f8.  The
  126.         value of the first radix is 8, the second is f, the third is 3.
  127.         Now the following example will make a bit more sense.
  128.  
  129.  
  130.         base 10 radix sort example
  131.  
  132.  
  133.         data           |first          |second
  134.         set            |pass           |pass
  135.         ---------------+---------------+---------------
  136.                        |               |
  137.         12             |09             |83
  138.         65             |38             |73
  139.         44             |37             |65
  140.         37             |65             |44
  141.         03             |44             |38
  142.         38             |03             |37
  143.         83             |83             |12
  144.         09             |73             |09
  145.         73             |12             |03
  146.  
  147.  
  148.                 The first pass through a radix sorting algorithm deals
  149.         ONLY with the least significant radix (in base 10, the least
  150.         significant radix is the one's place).  The data is sorted from
  151.         greatest to least (or least to greatest depending on the
  152.         application) based on the least significant radix.  After the
  153.         first pass, the data with the least significant radix of
  154.         greatest value is at the top of the list.
  155.  
  156.                 The second pass is similar to the first, with the
  157.         exception that the resultant data from the first pass is sorted
  158.         (NOT the original data), and the data is sorted based on the
  159.         second radix.  It is extremely important to preserve the order
  160.         of the previous pass, so make sure to traverse the list the
  161.         same way the original data was traversed in the first pass (in
  162.         this case, top to bottom).
  163.  
  164.                 Any additional passes to sort additional radices are
  165.         performed in the same manner, by sorting the data from the
  166.         previous pass with respect to the radix in question.
  167.  
  168.                 The radix sort has an advantage over the other sorts
  169.         presented here, because its sort time as a function of number
  170.         of data is linear.  The number of iterations needed in a radix
  171.         sort is given by (numData * numRadices) where numRadices is
  172.         constant for the entire data set.
  173.  
  174.  
  175.  
  176. THE BIT SORT (BASE 2 RADIX SORT)
  177.  
  178.                 Now that we have an algorithm that gives a linear
  179.         increase in the number of iterations needed to sort larger sets
  180.         of data, we need to find a way to make each iteration as fast
  181.         as possible.  This can be accomplished by changing the base in
  182.         which the data to be sorted is interpreted.  In base 10, we
  183.         have to go through each element of the set looking for a 9 in a
  184.         given radix, then look for an 8, etc.  This is quite slow, and
  185.         fairly difficult to implement on a computer.  A better approach
  186.         than using base 10 is to use base 2, where there are a total of
  187.         2 possible values for each radix (0 or 1).  It is very easy to
  188.         test whether or not a binary number contains a 1 in a given
  189.         place, this can be accomplished by an AND or TEST instruction.
  190.         Since there are only two possible values for a radix of base 2,
  191.         it is also extremely easy to sort from greatest to least based
  192.         on a given radix.  Simply put all the '1' radices at the top
  193.         and all the '0's at the bottom.  Here is some example code for
  194.         the bit sort applied to 16 bit data:
  195.  
  196.         // this requires two temporary arrays of [numData] elements,
  197.         // one for 1s and one for 0s
  198.  
  199.         short data[];                   // 16 bit data in this example
  200.         short oneArray[numData];
  201.         short zeroArray[numData];
  202.         int numOnes;
  203.         int numZeros;
  204.  
  205.         int mask = 1;
  206.  
  207.         for (count = 0; count < 16; count++)
  208.         {
  209.             numOnes = 0;
  210.             numZeros = 0;
  211.  
  212.             for (index = 0; index < numData; index++)
  213.             {
  214.                 if (data[index] & mask)
  215.                 {
  216.                     oneArray[numOnes] = data[index];
  217.                     numOnes++;
  218.                 }
  219.                 else
  220.                 {
  221.                     zeroArray[numZeros] = data[index];
  222.                     numZeros++;
  223.                 }
  224.             }
  225.  
  226.             // put the 1s back in the original data array first
  227.  
  228.             memcpy(data, oneArray, 2 * numOnes);
  229.  
  230.             // now put the 0s back
  231.  
  232.             memcpy(data + (2 * numOnes), zeroArray, 2 * numZeros);
  233.  
  234.             // mask out the next most significant bit next time through
  235.  
  236.             mask <<= 1;
  237.         }
  238.  
  239.                 This code is considerably faster than either the bubble
  240.         sort or the linear sort.  The inner loop is executed 16 *
  241.         numData times, and consists of three indirect references, one
  242.         TEST, one MOV, one INC, and one JZ/JMP (depending on the branch
  243.         taken) plus loop overhead.  The outer loop is actually more
  244.         costly than the inner loop because of the two block memory
  245.         transfers.  However, the outer loop is only executed 16 times
  246.         in this example.  Even so, this is a lot of iterations through
  247.         the loop.  If we could somehow find a way to cut down on the 16
  248.         iterations required per data element while keeping the inner
  249.         loop very simple, we could get a big increase in performance.
  250.  
  251.  
  252.  
  253. THE BYTE SORT (BASE 256 RADIX SORT)
  254.  
  255.  
  256.                 The obvious solution to this problem is to increase the
  257.         base of each radix examined.  The next logical base to use is
  258.         base 256, which can be represented in a single byte.  If we
  259.         were to implement the byte sort the same way we implemented the
  260.         base 10 radix sort in the original radix sort example, we would
  261.         look for a value of 255 in the least significant byte of each
  262.         data element, then look for a 254 in each element, etc.  This
  263.         would yeild (numData * 256 * 2 iterations) of the inner loop if
  264.         we used 16 bit data.  This would be nowhere near as fast as a
  265.         bit sort.
  266.  
  267.                 However, we can apply a bit of ingenuity to the byte
  268.         sort algorithm by taking a hint from the implementation of the
  269.         bit sort.  In the bit sort, we had a separate array for each
  270.         possible value of a given radix.  In a base 2 sort, there were
  271.         two possible values for each radix, therefore we had two
  272.         arrays.  If we extend this concept to a base 256 sort, we would
  273.         need 256 arrays, one for each possible value of a radix of base
  274.         256.  Now, following the bitsort algorithm, we would go through
  275.         the least significant byte of the data, placing the data in the
  276.         appropriate array which corresponds to the value of the least
  277.         significant radix.  We would of course repeat the procedure for
  278.         the next most significant radix and so on until all radices
  279.         have been considered.  In the case of 16 bit data, this method
  280.         would yeild numData * 2 iterations through the inner loop,
  281.         which is an 8 fold speed increase over the bit sort.
  282.  
  283.                 However, there is a rather large problem in the
  284.         implementation of the byte sort: memory.  In the implementation 
  285.         of the bit sort, it is fairly easy to organize code around two 
  286.         arrays.  However, a byte sort necessitates that the radix being 
  287.         examined be used as an index to an appropriate array (for 
  288.         example, a radix of value 4 would need to be placed in the '4s' 
  289.         array, a radix of value 33 would need to be placed in the '33s' 
  290.         array, etc).  Therefore, a two dimensional data structure needs 
  291.         to be used, with one dimension corresponding to the possible 
  292.         values of radices, and the other index corresponding to the 
  293.         actual data containing radices of a certain value.
  294.  
  295.                           <-- RADIX  -->
  296.  
  297.         ^   |00|01|02|03|04|05|06|07|08|09|0A|0B|0C|0D|0E|..|FC|FD|FE|FF
  298.         | --|-----------------------------------------------------------  
  299.           00|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |..|  |  |  |
  300.         D --|-----------------------------------------------------------
  301.         A 01|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |..|  |  |  |
  302.         T --|-----------------------------------------------------------
  303.         A ..|..|..|..|..|..|..|..|..|..|..|..|..|..|..|..|..|..|..|..|..
  304.           --|-----------------------------------------------------------
  305.         | nn|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |..|  |  |  |
  306.         v --------------------------------------------------------------
  307.  
  308.                 Our dilemma lies in the fact that there is no way 
  309.         whatsoever to determine the number of data that will contain a 
  310.         given radix at a given time.  Therefore, there is no way of 
  311.         knowing how large to make the dimension (nn) when initializing 
  312.         the data structure.  We could always make 256 arrays of 
  313.         [numData] elements each, but this would be extremely 
  314.         inefficient in that we would be allocating 256 times the memory 
  315.         we really need.
  316.  
  317.                 The solution to this problem lies in dynamic data 
  318.         structures.  By setting up an array of 256 linked lists, we can 
  319.         assure that we will not be allocating much more memory than we 
  320.         need.  The total overhead for a singly linked list is 4 bytes 
  321.         (the size of the starting list pointer), plus 4 bytes per data 
  322.         element.  Therefore, the total amount of storage needed for an 
  323.         array of 256 linked lists containing a total of numData 
  324.         elements is 4 * (256 + numData), only 1024 bytes more than we 
  325.         would need to store the data alone.
  326.  
  327.                 Now comes the task of selecting a data structure to fit 
  328.         our needs.  The two types of singly linked lists that could be 
  329.         used are stacks and queues.  I have no desire whatsoever to 
  330.         teach a course in data structures in this file; suffice to say 
  331.         that a stack is a last in first out (LIFO) structure, and a 
  332.         queue is a first in first out structure (FIFO).  In other 
  333.         words, the first value placed on a stack will be the last one 
  334.         removed, and the first value placed in a queue will be the 
  335.         first one removed.  I chose stacks because the operations to 
  336.         place (push) and remove (pop) values on and off the stack are 
  337.         faster than those for queues, and it is very easy to check to 
  338.         see if a stack is empty.  The LIFO nature of stacks complicates 
  339.         things a bit between loops, but within a loop a stack is by far 
  340.         the speediest option.
  341.  
  342.  
  343.                 Using stacks, the byte sort looks something like this
  344.  
  345.         typedef struct 
  346.         {
  347.             (polygon data goes here)
  348.  
  349.             ...
  350.  
  351.             // pointer to next polygon in the stack
  352.  
  353.             polygon *next;
  354.  
  355.         } polygon;
  356.  
  357.  
  358.         polygon *stack1[256], *stack2[256];     // our arrays of stacks
  359.  
  360.  
  361.         // this is the inner sort loop
  362.  
  363.         for (count = 0; count < numData; count++)
  364.         {
  365.             index = poly[count]->z & 0xFF;      // consider only the 
  366.                                                 // least significant radix
  367.  
  368.             push(stack1[index], poly[count]);   // put the poly in its 
  369.                                                 // proper place
  370.         }
  371.  
  372.                 That excruciatingly simple loop will sort the least 
  373.         significant byte.  Now, sorting the next most significant byte 
  374.         is a bit more complicated.  You must remember that the radix 
  375.         sort algorithm states we must sort the previously sorted data 
  376.         from greatest to least if we want our resultant data to be 
  377.         sorted from greatest to least.  So we must start with the 
  378.         highest value for the first radix and count backwards.  That 
  379.         means we need to start with the data on stack 255 and count 
  380.         down.
  381.  
  382.  
  383.         for (count = 255; count >= 0; count--)
  384.         {
  385.             while (!empty(stack1[count])
  386.             {
  387.                 temp = pop(stack1[count]);
  388.                 index = (temp->z & 0xFF00) >> 8; // next radix
  389.                 push(stack2[index], temp);
  390.             }
  391.         }
  392.  
  393.                 After this loop, the data will be in stack2[] with the 
  394.         smallest value at the top of stack2[0], and the largest value 
  395.         at the bottom of stack2[255].  From here, you can have your 
  396.         data sorted from least to greatest or greatest to least 
  397.         depending on how you put it back in the original poly[] array.
  398.  
  399.  
  400.  
  401. WELL...WHAT NOW?
  402.  
  403.                 If you are experienced with data structures, start 
  404.         coding.  If you are a bit dilenquent in your knowledge, start 
  405.         reading.  I recommend that you code the entire sort in 
  406.         assembler.  If you are smart about the way you set things up, 
  407.         your code will consist solely of MOV, AND, and SHL 
  408.         instructions with a JMP thrown in every once in awhile for 
  409.         good measure, and will occupy about 25 lines.  I have to 
  410.         confess that the assembler version of my sort is not the most 
  411.         highly optimized, simply because it is inherently so fast.  As 
  412.         I said before, my sort takes a whopping 5% of runtime.  Since 
  413.         the sort time of a radix sort is linear with respect to data 
  414.         size, this figure is the same whether you are sorting 10 
  415.         polygons or 10,000.  Before I spend long hours looking for 
  416.         places to save a cycle or two, I am going over the slower parts 
  417.         of my code and optimizing them.  However, I am positive I would 
  418.         have to spend a great deal of time optimizing my sort if I had 
  419.         used a slower algorithm.
  420.  
  421.  
  422.  
  423. FINAL WORDS
  424.  
  425.                 I am not interested in doing your coding for you.  I am 
  426.         happy to answer any questions you may have, but I will not 
  427.         write your code for you, and I refuse to teach a course in data 
  428.         structures.  If you don't understand basic stack operations, 
  429.         please don't ask me to explain them to you.  Any mail 
  430.         pertaining to this topic will be at best ignored, at worst 
  431.         returned accompanied by a polemic.
  432.  
  433.  
  434. GREETS & THANKS
  435.  
  436.         Siri                    - for being YOU!
  437.         Hurricane/OTM           - for continuing to give us direction
  438.         Zilym Limms/OTM         - for BWSB, and asm help
  439.         Phred/OTM               - 3d coalescence
  440.         Rest of OTM             - for surviving in the otherwise dead 602 
  441.         Rich Beerman            - we were going to...make a game? :>
  442.         Jailcoder               - first mentioned 'byte sort' to me 
  443.         Darkshade               - taught me the bit sort, many other things 
  444.         Daredevil and Tran      - pmode/w 
  445.         Otto Chrons             - for telling me what I am doing wrong 
  446.         Barry Egerter           - showed me how cool 640x480x256 looks 
  447.         Jmagic/Complex          - cool intro for TP94 
  448.         Phantom/Sonic PC        - show us a 3d demo already, will you? :>  
  449.         StarScream              - I want to see your vector code too :)
  450.         Kodiak_                 -\
  451.         ae-                     -  
  452.         Error                   -  For continued faith in the potential 
  453.         Omni                    -  of the North American scene 
  454.         ior                     -/
  455.  
  456.         Anyone else I forgot    - lame, cliche, copout greet phrase
  457.